/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 言初
 * Date: 2023-09-26
 * Time: 20:23
 */

public class test {
    //KMP算法
    //KMP算法的返回值是：返回子串在主串中的第一个下标（如果存在的话），不存在的话就返回-1
    public static int funcKmp(String str,String str1){
        //str是主串 ， str1是子串
        // 用i来表示str的下标位置
        // 用j来表示str1的下标位置
        int len=str.length();
        int len1=str1.length();
        int j=0;
        int i=0;
        int[] next=getNext(str1);
        //遍历主串
        while(i<len && j<len1){
            //这里的j==-1，是因为可能此时j下标的位置在0这个位置，然后并且第一个字符在这2个字符串中就不相等，所以说：
            // 为了防止数组越界，这里应该进到if里面
            // j==-1 的例子：主串：“abcdefghi” 子串：“gfb” 此时就会在比较过程中出现j==-1的情况了
            if(j==-1 || str.charAt(i)==str1.charAt(j)){
                j++;
                i++;
            }else{
                j=next[j];
            }
        }

        if(j==len1){
            //这是找到了
            return i-len1;
        }

        //这就代表没找到
        return -1;
    }
    //得到字符串的next数组
    public static int[] getNext(String str){
        int len=str.length();
        int[] next=new int[len];

        //是一个空字符串的话就直接返回了，不用进行任何操作了
        if(len<1){
            return next;
        }

        //只有一个字符的字符串
        //下表为0的位置，默认他对应的next数组的值为-1
        if(len==1){
            next[0]=-1;
            return next;
        }

        //有多个字符的字符串
        //下表为0的位置，默认他对应的next数组的值为-1
        //下标为1的位置，默认他对应的next数组的值为0
        if(len>1){
            next[0]=-1;
            next[1]=0;
        }
        int i=1;
        int k=0;

        while(i<len-1){
            if(k==-1){
                next[i+1]=k+1;
                k=next[i+1];
                i++;
            }else if(str.charAt(i)==str.charAt(k)){
                next[i+1]=k+1;
                k=next[i+1];
                i++;
            }else{
                k=next[k];
            }
        }
        //下标大于1的位置，他对应的next数组的值是按照规律进行计算的了
        // k下标就是此时这个i下标所对应的next数组中的值
        //按照一个公式，去找k下标和i下标相等的位置，
        // 如果找到了i和k下标相等的位置，就可以进行下一步了，
        // 要是没找到i和k下标相等的位置，就让k下标继续回退，直到相等或者k到达-1位置为止
        // 然后就可以求出 i+1 下标对应的next的值了,
        // next[i+1]= k+1;
        return next;
    }


    public static void main(String[] args) {
        System.out.println(funcKmp("ababcabcdabcdeabcdef","abcd"));//5
        System.out.println(funcKmp("aftdytdjxxwsrwsrtwshwftegjyf","shwfteg"));//18
        System.out.println(funcKmp("aftdytdjxxwsrwsrtwshwftegjyf","shwftg"));//-1
        System.out.println(funcKmp("aftdytdjxxwsrwsrtwshwftegjyf",""));//0
        System.out.println(funcKmp("","shwftg"));//-1
        System.out.println(funcKmp("",""));//0
        // System.out.println(funcKmp("ababcabcdabcdeabcdef","abcd"));
    }


    public static void main1(String[] args) {
        //测试getNext方法求字符串的next数组
        String str="abcababcabc";
        int[] ret=getNext(str);
        for(Integer s: ret){
            System.out.print(s+" ");
        }
    }
}

